二分圖最佳帶權匹配

二分圖最佳帶權匹配問題是指在給定帶權二分圖上求出一個最大匹配的問題，使得所有匹配邊權值之和最大。這個問題也被稱為二分圖最優匹配。

此類問題通常使用KM算法或轉換為一個網絡費用流問題進行求解。

定義

一個帶權二分圖 $G=(X,Y,E)$ 中的邊 $(u,v)\in E$ 都帶有一個權值 $f(u,v)$。該二分圖的一個最佳帶權匹配是它所有匹配中，所有匹配邊權值之和中最大的一個。

求解方法

KM算法

直接使用KM算法求解。

最小費用最大流

通過建立模型，使用費用流算法解決。

參考程序

C++

#include <cstdio>
#include <string.h>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int const MAX = 1000;
int const inf = INT_MAX;

int w[MAX][MAX];
int link[MAX];//代表当前与Y集合中配对的X集合中的点
int visx[MAX], visy[MAX];
int lx[MAX], ly[MAX];
int n, m;//代表X和Y中元素的个数
 
int can(int t)
{
    visx[t] = 1;
    for(int i = 1; i <= m; i++){
        if(!visy[i] && lx[t] + ly[i] == w[t][i]){//这里“lx[t]+ly[i]==w[t][i]”决定了这是在相等子图中找增广路的前提，非常重要
            visy[i] = 1;
            if(link[i] == -1 || can(link[i])){
                link[i] = t;
                return 1;
            }
        }
    }
    return 0;
}

int km(void)
{
    int sum = 0; memset(ly, 0, sizeof(ly));
    for(int i = 1; i <= n; i++){//把各个lx的值都设为当前w[i][j]的最大值
        lx[i] = -inf;
        for(int j = 1; j <= n; j++){
            if(lx[i] < w[i][j])
                lx[i] = w[i][j];
        }
    }

    memset(link, -1, sizeof(link));
    for(int i = 1; i <= n; i++){
        while(1){
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            if(can(i))//如果它能够形成一条增广路径，那么就break
                break;
            int d = inf;//否则，后面应该加入新的边,这里应该先计算d值
            for(int j = 1; j <= n; j++)//对于搜索过的路径上的XY点，设该路径上的X顶点集为S，Y顶点集为T，对所有在S中的点xi及不在T中的点yj
                if(visx[j])
                    for(int k = 1; k <= m; k++)
                       if(!visy[k])
                            d = min(d, lx[j] + ly[k] - w[j][k]);
            if(d == inf)
            return -1;//找不到可以加入的边，返回失败（即找不到完美匹配）
            for (int j = 1; j <= n; j++)
                if (visx[j])
                    lx[j] -= d;
            for(int j = 1; j <= m; j++)
                if(visy[j])
                    ly[j] += d;
            }
    }
    for(int i = 1; i <= m; i++)
        if(link[i] > -1)
            sum += w[link[i]][i];
    return sum;
}